package Matrix;
public class Matrix {
    /**
     *
     * @param p     p为矩阵链，p[0],p[1] 表示第一个矩阵的行数和列数，p[1],p[2]表示第二个矩阵的行数和列数........
     * @param n     n为p的长度
     * @param m     m为存储最优结果的二维矩阵
     * @param s     s为存储选择最优结果路线的
     */
    public static void MatrixChain(int[] p,int n, int[][] m, int[][] s) {
        for (int i = 1; i <= n; i++) {
            m[i][i] = 0;//m[i][i]只有一个矩阵，所以相乘次数为0，即m[i][i]=0
        }

        //r表示矩阵链的长度  l=2时，计算m[i][i+1]，i=1,2......n-1(长度l=2的链的最小代价)
        for(int r = 2;r <= n; r++ ) {
            for(int i = 1; i <= n-r+1; i++) {
                int j = i+r-1;//已i为起始位置,j为长度为l的链的末位
                m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
                s[i][j] = i;
                //k从i到j-1,以k为位置划分
                for(int k = i+1; k < j; k++) {
                    int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                    if(t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        }
    }
    public static void Traceback(int i, int j, int[][] s) {//打印输出矩阵连乘路线
        if(i == j) return;
        Traceback(i,s[i][j],s);
        Traceback(s[i][j] + 1,j,s);
        System.out.println("Multiply  A" + i + "," + s[i][j] + "and A" + (s[i][j] + 1) + "," + j);
    }
    public static void main(String[] args) {
        System.out.println("矩阵连乘测试结果为");
        Matrix mc = new Matrix();
        int n = 7;
        int p[] = { 30, 35, 15, 5, 10, 20, 25 };
        int m[][] = new int[n][n];
        int s[][] = new int[n][n];
        int l = p.length-1;
        mc.MatrixChain(p, l,m, s);
        System.out.println("矩阵连乘最少次数：");
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                System.out.printf( "%-9d",m[i][j]);
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("最优分解的k的值为：");
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                System.out.print(s[i][j]+" ");
            }
            System.out.println();
        }
        mc.Traceback( 1, 6, s);
    }
}